#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<math.h>
#include<Windows.h>
#define MAXNUM 512
#define INF 2147483647
using  namespace std;


struct Station //地铁站
{
	char Name[30];	//站名 
	int Transfer = 0;	//能否换乘 
	int id = 0;//id号
	int flag = 0;//距离某一个站点需要换乘的距离
};


struct vertex {				//地铁图结构体 
	char LineName[30];
	int weight;				//权重 
	int lineID;				//地铁路线序号 
	int speed;
};

struct Line
{
	Station station[50];
	int speed = { 0 };
	int distance[50] = { 0 };//距离上一个站点的距离
	char LineName[30];
	int len = { 0 };//长度
	int flag = { 0 };//距离某一个站点需要换乘的距离
};

struct Station StationID[MAXNUM];	//数组用于记录地铁站序号
struct vertex map[MAXNUM][MAXNUM];			//地铁图 
struct Line line[30];
int lineID;		//路线序号
int StationNum;	//一条路线中地铁站个数
char LineName[30];//地铁路线名
int speed;//线路速度
int isloop;//是否环线
int distance;//站间距离
int Transfer;	//是否换乘
int lineNum;	//路线个数
int TotalNum = 0;	//总地铁站个数 
int distsum;
int previous[MAXNUM];	//跟踪数组
int dist[MAXNUM];	//最短路径数值数组
int path[MAXNUM];	//Dijkstra最短路径编号数组
int top;	//栈顶
char Begin[30], Destination[30];	//起点站，终点站 
void InitMap();	//初始化图
void CreateMap(FILE* fp);	//读取地铁站点信息，并建立图 
int SearchName(char* s, int flag);	//查询站名是否已出现过 
void Dijkstra(int vs, int ve);		//实现Dijkstra算法找到最短路径
void PrintRoute(int s1, int s2);	//打印换乘路线
void Dijkstraleaststation(int s1, int s2);//找到最少站点
void Dijkstraleasttime(int s1, int s2);	//实现Dijkstra算法所需最少时间
int searchLINE(char* s, int flag);	//查询站名是否已出现过 
int searchSpeed(char* s, int flag);	//查询站名是否已出现过 
void color(int n);//用于设置颜色美化

int main()
{
	int chan = 0;
	int zhan = 0;
	int tran = 0;
	char zhanname[10];
	int distance;
	int k;
	int speed;
	char linename[16];
	int id;
	int chan2 = 0;
	FILE* fp = fopen("C:/data.txt", "r");



	InitMap();
	CreateMap(fp);		//建图 

	while (true) {
		color(14);
		cout << endl << "◤▲▼▲▼▲▼▲▼▲▼▲▼▲▼▲2021213550▲▼▲▼▲▼▲▼▲▼▲▼▲▼▲◥" << endl << endl;
		color(3);
		cout << "                            欢迎使用北京地铁导航" << endl << endl;
		color(15);
		cout << "输入1，进行路线规划" << endl;
		cout << "输入2，进行站点添加" << endl;
		cout << "输入3，进行线路删除" << endl;
		scanf("%d", &chan);
		switch (chan)
		{
		case 1:
		{cout << "请输入起点站和终点站（用空格分开）：";

		int s1, s2, temp;

		scanf("%s %s", Begin, Destination);
		cout << endl << "输入1，2，3选择不同的策略：" << endl;
		cout << "1.最短距离" << endl;
		cout << "2.最少换乘次数" << endl;
		cout << "3.最短时间" << endl;
		scanf("%d", &chan2);

		s1 = SearchName(Begin, 1);	//找到起点站编号 
		s2 = SearchName(Destination, 1);	//找到终点站编号  
		switch (chan2)
		{
		case 1:
			Dijkstra(s1, s2);	//找最短路 
			top = 0;
			for (temp = s2; temp != s1; temp = previous[temp])	//路径追溯 
			{
				path[top] = temp;
				top++;
			}
			cout << endl << "最短距离路线是";

			PrintRoute(s1, s2);	//打印编号 
			break;
		case 2:
			cout << endl << "最少换乘次数路线是" << endl;
			Dijkstraleaststation(s1, s2);
			//cout << "距离" << distsum << "米" << endl;
			break;
		case 3:
			Dijkstraleasttime(s1, s2);
			top = 0;
			for (temp = s2; temp != s1; temp = previous[temp])	//路径追溯 
			{

				path[top] = temp;
				top++;
			}

			cout << endl << "最短时间路线是";
			PrintRoute(s1, s2);	//打印编号 
			break;
		default:
			break;
		}

		break; }
		case 2:
		{cout << "请输入它的站点名称,是否为换乘站（空格隔开，1表示换乘）" << endl;

		scanf("%s %d(用01表示)", &zhanname, &tran);
		strcpy(StationID[TotalNum].Name, zhanname);	//保存站名和换乘信息 
		StationID[TotalNum].Transfer = tran;
		cout << "请输入它要与几个站点连接；";
		scanf("%d", &zhan);
		for (int i = 0; i < zhan; i++) {
			printf("第%d个站录入，请依次输入相邻站名，距离，路线名字（以空格分开）:", i + 1);
			scanf("%s %d %s", &zhanname, &distance, &linename);
			k = SearchName(zhanname, 0);
			strcpy(map[k][TotalNum].LineName, linename);
			strcpy(map[TotalNum][k].LineName, linename);
			map[k][TotalNum].weight = map[TotalNum][k].weight = distance;
			speed = searchSpeed(linename, 1);
			map[k][TotalNum].speed = map[TotalNum][k].speed = speed;
			id = searchLINE(linename, 1);
			map[k][TotalNum].lineID = map[TotalNum][k].lineID = id;
		}

		TotalNum++; }
		break;
		case 3:
		{cout << "请选择删除哪个路线：" << endl;
		scanf("%s", &zhanname);

		k = searchLINE(zhanname, 0);

		for (int i = 0; i < 50; i++) {
			line[k].station[i].id = 0;
			strcpy(line[k].station[i].Name, "   ");
			line[k].station[i].flag = 0;
		}
		line[k].flag = 0;
		line[k].len = 0;
		strcpy(line[k].LineName, " ");
		cout << "已经删除完成  " << endl; }
		break;
		default:
			break;
		}

	}
	return 0;
}



void InitMap()//初始化图 
{
	int i, j;
	for (i = 0; i < MAXNUM; i++)
	{
		for (j = 0; j < MAXNUM; j++)
		{
			map[i][j].weight = map[j][i].weight = INF;	//权重初始化为无穷大 
			map[i][j].speed = map[j][i].speed = 0;
			map[i][j].lineID = map[j][i].lineID = 0;//编号为0 
			map[i][j].lineID = map[j][i].lineID = 0;//编号为0 
		}
	}
}


void CreateMap(FILE* fp)	//读取地铁站点信息，并建立图 
{
	int i, j;
	int ExistID, cur;	//存在站点的编号，边的起点 
	char Name[30];		//站名 
	int distance = 0;
	fscanf(fp, "%d", &lineNum);

	for (i = 0; i < lineNum; i++)	//遍历读取所有线路信息
	{
		fscanf(fp, "%d %s %d %d %d", &lineID, LineName, &StationNum, &speed, &isloop);
		//cout<<"linenum:" << lineID<<"   "<<i<<"  "<< LineName<<"     " <<StationNum<<"speed"<<speed<< endl;
		cur = -1;	//初始化为-1 

		strcpy(line[lineID].LineName, LineName);
		line[lineID].len = StationNum;
		line[lineID].speed = speed;

		for (j = 0; j < StationNum; j++)
		{
			//cout << "station:" << j << endl;

			//cout << line[7].LineName<<"i:"<<i<<"j:"<<j<<"   ";
			if (j < StationNum - 1)
			{
				fscanf(fp, "%s %d %d", Name, &Transfer, &distance);
			}
			else
			{
				fscanf(fp, "%s %d", Name, &Transfer);//线路最后一行没有距离
			}

			strcpy(line[lineID].station[j].Name, Name);
			line[lineID].distance[j] = distance;
			ExistID = SearchName(Name, 0);	//站名是否存在
			//cout<<"name"<<Name<<" TotalNum :  " << TotalNum <<" ExistID "<<ExistID<< endl;
			if (ExistID == -1)		//不存在 
			{
				strcpy(StationID[TotalNum].Name, Name);	//保存站名和换乘信息 
				StationID[TotalNum].Transfer = Transfer;
				line[lineID].station[j].id = TotalNum;
				if (cur != -1)		//若有边的起点 
				{
					//cout << "  " << cur << "  " << TotalNum<< "lineid "<<lineID<<endl;
					map[cur][TotalNum].lineID = map[TotalNum][cur].lineID = lineID;	//保存线路和权重
					map[cur][TotalNum].weight = map[TotalNum][cur].weight = distance;
					map[cur][TotalNum].speed = map[TotalNum][cur].speed = speed;
					strcpy(map[cur][TotalNum].LineName, LineName);
					strcpy(map[TotalNum][cur].LineName, LineName);
				}

				cur = TotalNum;	//终点变起点 
				TotalNum++;		//更新总数
			}

			else
			{
				line[lineID].station[j].id = ExistID;
				if (cur != -1)	//若有边的起点 
				{

					map[cur][ExistID].lineID = map[ExistID][cur].lineID = lineID;//保存线路和权重
					map[cur][ExistID].weight = map[ExistID][cur].weight = distance;
					map[cur][ExistID].speed = map[ExistID][cur].speed = speed;
					//map[cur][TotalNum].speed = map[TotalNum][cur].speed = speed;
					strcpy(map[cur][TotalNum].LineName, LineName);
					strcpy(map[TotalNum][cur].LineName, LineName);
				}

				cur = ExistID;	//终点变为起点
			}
		}
	}
}




int searchLINE(char* s, int flag) {
	int i;
	//cout << TotalNum;
	for (i = 0; i < TotalNum; i++)
	{
		if (strcmp(s, map[i][i + 1].LineName) == 0) {
			return map[i][i + 1].lineID;	//返回序号 
		}
	}
	if (flag == 1) {
		cout << "你输入的路线名有误" << endl;
	}
	return -1;
}

int searchSpeed(char* s, int flag)
{
	int i;
	for (i = 0; i < TotalNum; i++)
	{
		if (strcmp(s, map[i][i + 1].LineName) == 0) {
			return map[i][i + 1].speed;	//返回序号 
		}
	}
	if (flag == 1) {
		cout << "你输入的路线名有误" << endl;
	}
	return -1;

}


int SearchName(char* s, int flag)
{
	int i;
	for (i = 0; i < TotalNum + 1; i++)
	{
		if (strcmp(s, StationID[i].Name) == 0) {
			return i;	//返回序号 
		}
	}
	if (flag == 1) {
		cout << "你输入的地点有误" << endl;
	}
	return -1;
}


int getlineid(char* s1, char* s2) {
	int flags1 = 0;
	int flags2 = 0;
	for (int i = 0; i < 30; i++) {
		flags1 = flags2 = 0;
		for (int j = 0; j < 50; j++) {
			if (strcmp(line[i].station[j].Name, s1) == 0) {
				flags1 = 1;
			}
			if (strcmp(line[i].station[j].Name, s2) == 0) {
				flags2 = 1;
			}
			if (flags1 + flags2 == 2) {
				return i;
			}
		}
	}
	return -1;
}


int getline(char* s1, int i) {
	i++;
	for (; i < 30; i++) {
		for (int j = 0; j < 50; j++) {
			if (strcmp(line[i].station[j].Name, s1) == 0) {
				return i;
			}
		}
	}
	return 0;
}//set是返回第几个站点

int getid_online(char* s1, int i) {


	for (int j = 0; j < 50; j++) {
		if (strcmp(line[i].station[j].Name, s1) == 0) {
			return j;
		}
	}
	return -1;
}



void Dijkstra(int s1, int s2)	//实现Dijkstra算法找到最短路径
{
	int i, j;
	int k = 0;
	int min, tmp;
	int flag[MAXNUM] = { 0 };  // 为1时到"顶点i"的最短路径已获取。

	for (i = 0; i < TotalNum; i++)	// 初始化
	{
		flag[i] = 0;              	// 初始化为0，最短路径未找到
		previous[i] = s1;
		dist[i] = map[s1][i].weight;	//最短路径为s1到i的权重
	}

	dist[s1] = 0;
	flag[s1] = 1;		// 顶点s1初始化

	for (i = 0; i < TotalNum - 1; i++)	// 每遍历1次找到1个顶点的最短路径
	{
		min = INF;
		for (j = 0; j < TotalNum; j++)	// 找离s1最近的顶点k
		{
			if (flag[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				k = j;
			}
		}

		flag[k] = 1;				// 标记k找到最短路径

		//更新未获取最短路径的顶点的最短路径和前驱
		for (j = 0; j < TotalNum; j++)
		{
			tmp = (map[k][j].weight == INF ? INF : (min + map[k][j].weight)); // 避免溢出
			if (flag[j] == 0 && (tmp < dist[j]) && map[k][j].lineID > 0)
			{
				dist[j] = tmp;
				previous[j] = k;	//前驱 
			}
		}
	}

	return;
}



int getabs(int lineid, int s1, int s2) {//获取一条链上两个站之间的相差的站数
	int a = 0;
	int b = 0;
	for (int i = 0; i < 50; i++) {
		if (line[lineid].station[i].id == s1) {
			a = i;
		}
		if (line[lineid].station[i].id == s2) {
			b = i;
		}
	}
	return a - b > 0 ? a - b : b - a;
}


void Dijkstraleaststation(int s1, int s2)	//实现Dijkstra算法找到最少站点
{
	int i, j;
	int idm = 0, idn = 0;
	int distsum = 0;
	int set = 0;
	int doneflag = 0;
	int k = 0;
	int nongdu = 30;
	int newi = 0, newj = 0;//新坐标
	int lineid;
	int add = 0;
	int min = 50;
	int ida, idb;
	for (int i = 1; i < lineNum + 1; i++) {
		for (int j = 0; j < line[i].len; j++) {
			if (line[i].station[j].id == s1) {
				line[i].station[j].flag = 1;
				StationID[line[i].station[j].id].flag = 1;
			}
		}
	}
	while (true)
	{
		for (int done = 0; done < 23; done++) {
			for (i = 1; i < lineNum + 1; i++) {
				min = 50;
				for (j = 0; j < line[i].len; j++) {

					if (StationID[line[i].station[j].id].flag != 0) {
						if (StationID[line[i].station[j].id].flag < min) {
							line[i].flag = StationID[line[i].station[j].id].flag + 1;
							min = line[i].flag;
						}
					}
				}

				for (j = 0; j < line[i].len; j++) {
					//当两者为0先赋值，当s不为0时，先进行一下比较
					if ((StationID[line[i].station[j].id].flag == 0) && (line[i].station[j].flag == 0)) {
						StationID[line[i].station[j].id].flag = line[i].flag;
						line[i].station[j].flag = line[i].flag;
					}
					else if (StationID[line[i].station[j].id].flag > line[i].flag) {
						StationID[line[i].station[j].id].flag = line[i].flag;
						line[i].station[j].flag = line[i].flag;
					}
					else {
						line[i].station[j].flag = StationID[line[i].station[j].id].flag;
					}
				}
			}
			for (int i = 1; i < lineNum + 1; i++) {
				for (int j = 0; j < line[i].len; j++) {
					line[i].station[j].flag = StationID[line[i].station[j].id].flag;
				}
			}
		}
		add++;
		cout << 1;
		if (doneflag == 0) {//找到之后，向低浓度地区转移
			for (int i = 1; i < lineNum + 1; i++) {
				for (int j = 0; j < 50; j++) {
					if (line[i].station[j].id == s2) {
						//cout << line[i].station[j].id << "  " << i << "  " << j << endl;
						nongdu = line[i].station[j].flag;
						newi = i;
						newj = j;

					}
				}
			}
			printf("%s", line[newi].station[newj].Name);

			while (true)
			{
				for (int i = 1; i < lineNum + 1; i++)
				{

					for (int j = 0; j < 50; j++)
					{
						if (line[i].station[j].flag == nongdu - 1 && getid_online(line[newi].station[newj].Name, i) != -1) {
							lineid = getlineid(line[newi].station[newj].Name, line[i].station[j].Name);

							ida = getid_online(line[newi].station[newj].Name, lineid);
							idb = getid_online(line[i].station[j].Name, lineid);
							if (ida <= idb)
							{
								idm = ida;
								idn = idb;
							}
							else {
								idm = idb;
								idn = ida;
							}

							for (int k = idm; k <= idn; k++)
							{
								distsum += line[lineid].distance[k];
								//cout << distsum << endl;
							}

							printf("-->%s(%d站)-->%s", line[lineid].LineName, getabs(lineid, line[newi].station[newj].id, line[i].station[j].id), line[i].station[j].Name);
							newi = i;
							newj = j;
							nongdu--;
							if (nongdu <= 1)
							{
								cout << endl;
								cout << "距离：" << distsum << endl;
								return;
							}
						}
					}
				}
				if (nongdu <= 0) {
					return;
				}
			}
		}
	}

	return;
}




void Dijkstraleasttime(int s1, int s2)	//实现Dijkstra算法所需最少时间
{
	int i, j;
	int k = 0;
	float min, tmp;
	int flag[MAXNUM] = { 0 };  // 为1时到"顶点i"的最短路径已获取。

	float distf[MAXNUM] = { 0 };
	for (i = 0; i < TotalNum; i++)	// 初始化
	{
		flag[i] = 0;              	// 初始化为0，最短路径未找到
		previous[i] = s1;
		distf[i] = (map[s1][i].weight == INF ? INF : map[s1][i].weight * 1.0 / map[s1][i].speed);	//最短路径为s1到i的权重

	}

	distf[s1] = 0;
	flag[s1] = 1;		// 顶点s1初始化

	for (i = 0; i < TotalNum - 1; i++)	// 每遍历1次找到1个顶点的最短路径
	{
		min = INF;
		for (j = 0; j < TotalNum; j++)	// 找离s1最近的顶点k
		{
			if (flag[j] == 0 && distf[j] < min)
			{
				min = distf[j];
				k = j;
			}
		}

		flag[k] = 1;				// 标记k找到最短路径

		if (k == s2)	return;
		//更新未获取最短路径的顶点的最短路径和前驱
		for (j = 0; j < TotalNum; j++)
		{
			tmp = (map[k][j].weight == INF ? INF : (min + map[k][j].weight * 1.0 / map[k][j].speed)); // 避免溢出
			if (flag[j] == 0 && (tmp < distf[j]) && map[k][j].lineID > 0)
			{
				distf[j] = tmp;
				previous[j] = k;	//前驱 
			}
		}
	}
}

void color(int n)//用于设置颜色美化
{
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), n);
	return;
}

void PrintRoute(int s1, int s2)
{
	int i;
	int cur = s1, Len = 1;//边的起点，长度
	int des = path[top - 1];//边的终点 
	int money;

	int change = 0;

	int lineId = getlineid(StationID[s1].Name, StationID[path[top - 1]].Name);	//开始路线编号 
	int distance1 = 0;
	for (int i = 0; i < line[lineId].len; i++) {
		if (line[lineId].station[i].id == s1 || line[lineId].station[i].id == path[top - 1])
		{
			//cout << i;
			distance1 = line[lineId].distance[i];
			break;
		}
	}
	float time = distance1 * 0.12 / line[lineId].speed;
	printf("\n换乘路线如下：\n\n");
	//cout << getlineid(StationID[s1].Name, StationID[path[top - 2]].Name) << endl;
	//cout << line[getlineid(StationID[s1].Name, StationID[path[top - 2]].Name)].LineName << endl;
	printf("%s--%s", StationID[s1].Name, line[getlineid(StationID[s1].Name, StationID[path[top - 2]].Name)].LineName);	//打印起点站和起点站的路线 

	cur = des;
	for (i = top - 2; i >= 0; i--)	//利用栈倒过来寻找 
	{
		des = path[i];	//更新终点 
		distance1 = distance1 + map[path[i]][path[i + 1]].weight;
		//cout <<endl<< "上一站" << StationID[path[i + 1]].Name << "  这一战：" << StationID[path[i]].Name<< map[path[i]][path[i + 1]].weight<<endl;
		time = time + map[path[i]][path[i + 1]].weight * 0.12 / line[getlineid(StationID[path[i]].Name, StationID[path[i + 1]].Name)].speed;
		if (lineId != map[cur][des].lineID)	//换乘 
		{
			change++;
			printf("(%d站)-->%s--%s", Len, StationID[cur].Name, line[getlineid(StationID[path[i]].Name, StationID[path[i + 1]].Name)].LineName);
			lineId = map[cur][des].lineID;
			Len = 0;
		}
		Len++;		//长度 +1 
		cur = des;	//更新起点
	}

	if (distance1 <= 6000)
		money = 3;
	else if (6000 < distance1 && distance1 <= 12000)
		money = 4;
	else if (12000 < distance1 && distance1 <= 22000)
		money = 5;
	else if (22000 < distance1 && distance1 <= 32000)
		money = 6;
	else if (distance1 > 32000)
		money = ceil((distance1 - 32000) * 1.0 / 20000) + 6;

	printf("(%d站)-->%s\n", Len, StationID[s2].Name);
	printf("距离： %d  时间： %.2f 分钟  换乘次数：%d  费用：%d 元", distance1, time, change, money);
}